第五讲 凸集及其分离
标准的最优化问题
标准的最优化问题:在标量约束\(G(x) \leq c\) 下选择向量\(x\) 以最大化\(F(x)\)。
等值线:对于一个多变量函数\(F(x)\) 而言,使得函数值等于\(c\) 的所有可能的向量\(x\) 共同构成一条等值线,对应优化问题中的约束条件。e.g. 预算约束线,等利润线,无差异曲线
上等值集:所有满足\(F(x) \geq v\) 的向量\(x\) 共同构成的集合
下等值集:所有满足\(G(x) \leq c\) 的向量\(x\) 共同构成的集合
凸集的分离性质
凸集(convex set)
定义: 对于\(n\) 维空间中的点集\(S\) 而言,如果给定\(S\) 中的任意两点\(x^a = (x_1^a, \cdots, x_n^a)\) 和\(x^b = (x_1^b, \cdots, x_n^b)\) 以及闭区间\([0,1]\)中的任意实数\(\theta\),点\(\theta x^a + (1-\theta)x^b\) 也在点集\(S\) 中,那么称点集\(S\) 是凸的(convex)。
生产函数的下等值集是凸集,意味着什么?
效用函数的上等值集是凸集,意味着什么?
凸函数
定义1(从函数出发): 如果一个函数\(G(x)\)满足,对于所有的\(x^a, x^b\)和任意\(\theta \in [0,1]\),都有 \[ G(\theta x^a + (1 - \theta)x^b) \leq \theta G(x^a) + (1 - \theta)G(x^b) \] 则称其为凸函数(convex function)。
反之,若一个函数\(F(x)\)满足 \[ F(\theta x^a + (1 - \theta)x^b) \geq \theta F(x^a) + (1 - \theta)F(x^b) \] 则称其为凹函数(concave function)。
凹函数
拟凸函数
从代数上看,集合\(G(x)\leq c\) 是凸集意味着: \[ G(x^a) \leq c , G(x^b) \leq c \Rightarrow G(\theta x^a + (1 - \theta) x^b) \leq c \]
如果其中一个端点的值恰好等于\(c\) 时,这个条件又可以表述为\(\forall x^a, x^b , \theta \in[0,1]\): \[ G(\theta x^a + (1 - \theta) x^b) \leq max(G(x^a), G(x^b)) \]
我们称满足上述条件的函数为拟凸函数(quasi convex function)。
反之,如果函数\(F(x)\)满足 \[ F(\theta x^a + (1 - \theta) x^b) \geq min(F(x^a), F(x^b)) \] 则称其为拟凹函数(quasi concave function)。
内点与边界点
内点:如果存在点\(x^0\) 的邻域\(B(x^0, \delta)\) 包含于集合\(S\),则称点\(x^0\) 是集合\(S\) 的一个内点(inner point)
边界点:如果一个点\(x^1\) 既不是集合\(S\)的内点,也不是集合\(S\) 的补集的内点,则称点\(x^1\) 是集合\(S\)的一个边界点(boundary points)。换言之,如果一个点\(x^1\)是集合\(S\) 的边界点,那么其任意邻域内,都既存在属于\(S\)的点,也存在不属于\(S\)的点
分散化下的局部失灵
分离定理
如果A和B为两个没有公共内点的凸集,且至少有一个集合有一个非空内点,那么我们总可以找到一个非零向量\(p\)和一个数\(b\),使得超平面\(px = b\)分离这两个集合,或:
\[ px \begin{cases} \leq b, & \forall x \in A \\ \geq b, & \forall x \in B \end{cases} \]
分离角度的最优化定理
给定拟凹函数\(F\)和拟凸函数\(G\),点\(\bar{x}\)在满足约束条件\(G(x) \leq c\)下使得\(F(x)\)最大,当且仅当存在一个非零向量\(p\),使得:
\(\bar{x}\)在满足\(G(x) \leq c\)下最大化\(px\)
\(\bar{x}\)在满足\(F(x) \geq \bar{v}\)下最小化\(px\)
经济学解释
假定\(x\)为生产-消费向量,约束反映了资源的有限性,目标函数为效用函数。\(p\)理解为产出的价格向量,那么上述定理意味着:
寻求产出价格最大化的企业家会生产出最优产量\(\bar{x}\)
试图以最小支出达到既定效用的消费者也恰好需要\(\bar{x}\)
社会最优化问题就可以被分散化的机制实现
唯一性
严格拟凸
严格拟凸函数: \[ G(\theta x^a + (1 - \theta) x^b) < max(G(x^a), G(x^b)) \]
严格拟凹函数: \[ F(\theta x^a + (1 - \theta) x^b) > min(F(x^a), F(x^b)) \]
唯一性条件
考虑在约束\(G(x) \leq c\) 下最大化\(F(x)\)的问题,其中\(F\)为严格拟凹的,\(G\)为严格拟凸的。假定\(x\)满足分离角度的最优化定理,那么它将是该最优化问题的唯一解。【证明:反证法】